/*
 * covertree.h
 *
 *  Created on: Mar 1, 2011
 *      Author: tqlong
 */

#ifndef COVERTREE_H_
#define COVERTREE_H_

#include "tree.h"

template<typename T>
class CoverTreeNode : public TreeNode<T>
{
public:
  typedef TreeNode<T>                    __Base;
  typedef typename __Base::iset_type     iset_type;
  typedef typename __Base::pset_type     pset_type;
  typedef typename __Base::vec_type      vec_type;
  typedef typename __Base::nodelist_type nodelist_type;
  typedef std::vector<CoverTreeNode<T>*> coverset_type;
protected:
  double level_;
  bool self_child_;
public:
  /** Root constructor */
  CoverTreeNode(pset_type& p, iset_type& idx)
    : __Base(p, idx) {}
  /** Child constructor */
  CoverTreeNode(CoverTreeNode& parent, int lo, int hi_ex, double level, bool self_child)
    : __Base(parent, lo, hi_ex), level_(level), self_child_(self_child) {}
  CoverTreeNode* child(unsigned int i) const { return static_cast<CoverTreeNode*>(__Base::child(i)); }

  /** The center point is the first point */
  const vec_type& center() const { return this->point(0); }

  double level() const { return level_; }
  bool self_child() const { return self_child_; }

  /** Tree build functions */
  void prepareRoot();
  void split();
  void splitRecursive();

protected:
  /** static functions for nearest neighbors */
  static bool reachLeaf(const vec_type& p, const coverset_type &Q_l, int &minIdx);
  static bool reachLeafAll(const CoverTreeNode& P, const coverset_type &Q_l, std::vector<int>& minIdx);
  static double distanceToChild(const vec_type& p, const coverset_type &Q_l, double l);
  static void nextCoverSet(const vec_type& p, const coverset_type &Q_l,
                           double l, double bound, coverset_type &Q_lm1);
public:
  static int nearest(const vec_type& p, const coverset_type &Q_l, double l);
  static int nearest(const vec_type& p, CoverTreeNode& root);
  static void allNearest(const CoverTreeNode& P, const coverset_type &Q_l,
                         double lP, double lQ, std::vector<int>& minIdx);
  static void allNearest(CoverTreeNode& P, CoverTreeNode& Q, std::vector<int>& minIdx);

  void print();
};

//template<typename T>
//int nearest(const T& p, const typename CoverTreeNode<T>::coverset_type& Q_l, double l);

#include "covertree_impl.h"
#endif /* COVERTREE_H_ */
